package com.zdb.datastructures.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Graph {

    // 存储顶点的集合
    private List<String> vertexList;

    private Map<String, Integer> vertex2index;

    // 存储图对应的邻接矩阵
    private int[][] edges;
    // 表示边的数量
    private int numOfEdges;

    // true表示对应节点访问过了
    private boolean[] isVisited;

    public Graph(int n) {
        edges = new int[n][n];
        vertexList = new ArrayList<>(n);
        vertex2index = new HashMap<>(n);
        isVisited = new boolean[n];
        numOfEdges = 0;
    }

    public void insertVertex(String vertex) {
        vertexList.add(vertex);
        vertex2index.put(vertex, vertexList.size() -1);
    }

    public void insertEdge(int v1, int v2, int weight) {
        if(edges[v1][v2] == 0) {
            numOfEdges ++;
        }
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
    }

    public void dfs() {
        isVisited = new boolean[vertexList.size()];
        List<String> result = new ArrayList<>(vertexList.size());
        result.add(vertexList.get(0));
        isVisited[0] = true;
        dfs(vertexList.get(0), result);
        System.out.println(result);
    }

    public void bfs() {
        isVisited = new boolean[vertexList.size()];
        List<String> result = new ArrayList<>(vertexList.size());
        result.add(vertexList.get(0));
        isVisited[0] = true;
        bfs(vertexList.get(0), result);
        System.out.println(result);
    }

    /**
     * 广度优先遍历
     * broad first search
     * @param vertex
     * @param result
     */
    public void bfs(String vertex, List<String> result) {
        System.out.println("bfs:" + vertex + ",当前结果：" + result);
        int vIndex = vertex2index.get(vertex);
        List<String> nextVertexs = new ArrayList<>();
        // 先把当前可以访问的节点遍历
        for (int i = 0; i < vertexList.size(); i++) {
            // 不是当前节点，且未被访问，且有边连接，说明可以访问
            if(i != vIndex
                    && !isVisited[i]
                    && edges[i][vIndex] > 0) {
                isVisited[i] = true;
                result.add(getValueByIndex(i));
                nextVertexs.add(getValueByIndex(i));
            }
            // 可以判断是否所有节点都已经访问了，如果都访问了跳出循环
        }

        // 再将新访问到的节点当做当前节点继续遍历
        for(String v : nextVertexs) {
            bfs(v, result);
        }
    }

    /**
     * 深度优先遍历
     * depth first search
     * @param vertex 当前节点
     */
    public void dfs(String vertex, List<String> result) {
        System.out.println("dfs:" + vertex + ",当前结果：" + result);
        int vIndex = vertex2index.get(vertex);
        for (int i = 0; i < vertexList.size(); i++) {
            // 不是当前节点，且未被访问，且有边连接，说明可以访问
           if(i != vIndex && !isVisited[i] && edges[i][vIndex] > 0) {
                isVisited[i] = true;
                result.add(getValueByIndex(i));
                dfs(getValueByIndex(i), result);
           }
        }
    }

    public void insertEdge(String vertex1, String vertex2, int weight) {

        int v1 = vertex2index.get(vertex1);
        int v2 = vertex2index.get(vertex2);

        if(edges[v1][v2] == 0) {
            numOfEdges ++;
        }

        edges[v1][v2] = weight;
        edges[v2][v1] = weight;

    }

    public int getWeight(int x, int y) {
        return edges[x][y];
    }

    public String getValueByIndex(int index) {
        return vertexList.get(index);
    }

    public void showGraph() {
        for(int[] link : edges) {
            System.err.println(Arrays.toString(link));
        }
    }

    public int getNumOfVertex() {
        return vertexList.size();
    }

    public int getNumOfEdges() {
        return numOfEdges;
    }

    public static void main(String[] args) {
        int n = 5;
        String vertes[] = {"A", "B", "C", "D", "E"};

        Graph graph = new Graph(n);
        for(String vertex : vertes) {
            graph.insertVertex(vertex);
        }

        // 插入边
        graph.insertEdge("A", "C", 1);
        graph.insertEdge("A", "B", 1);
        graph.insertEdge("B", "C", 1);
        graph.insertEdge("B", "D", 1);
        graph.insertEdge("B", "E", 1);

        graph.showGraph();

        graph.dfs();
        graph.bfs();
    }

}
